import org.junit.Test;

public class Solution1028 {
    /**
     * 输入："1-2--3--4-5--6--7"
     * 输出：[1,2,5,3,4,6,7]
     * <p>
     * 输入："1-2--3---4-5--6---7"
     * 输出：[1,2,5,3,null,6,null,4,null,7]
     * <p>
     * 输入："1-401--349---90--88"
     * 输出：[1,401,null,349,88,90]
     */
    int pos;

    public TreeNode recoverFromPreorder(String S) {
        if (S == null || S.length() == 0) return null;
        TreeNode head = new TreeNode(val(S));
        head.left = dps(0, S);
        head.right = dps(0, S);
        return head;
    }

    public TreeNode dps(int deep, String S) {
        if (pos >= S.length()) return null;
        int curDeep = deep + 1;
        deep = 0;
        char c = S.charAt(pos);
        while (c == '-') {
            deep++;
            c = S.charAt(++pos);
        }
        if (deep != curDeep) {
            pos -= deep;
            return null;
        }
        TreeNode node = new TreeNode(val(S));
        node.left = dps(curDeep, S);
        node.right = dps(curDeep, S);
        return node;
    }


    public int val(String s) {
        int val = 0;
        while (pos < s.length() && '0' <= s.charAt(pos) && s.charAt(pos) <= '9')
            val = val * 10 + (s.charAt(pos++) - '0');
        return val;
    }

}
